package shell;

public class Shell02 {
    public static void sort(int[] arr){
        int h = 1;
        while(h <= arr.length/3){
            h = h*3 + 1;
        }
        for(int gap = h; gap > 0; gap = (gap-1)/3){
            //内部还是插入排序
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                while(j > gap - 1 && temp < arr[j-gap]){
                    arr[j] = arr[j-gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }
}
